1. Field of the Invention
The present invention relates to a wiring processing method, wiring processing equipment, and recording medium for a wiring processing program suitable for use in designing a large scale integrated circuit (LSI) using the computer aided design (CAD) system.
In clock nets on a clock distributing circuit of a clock synchronous circuit, to equalize the delay time (propagation delay time of a clock) from a clock generator (driver) to each of clock receivers, namely, to decrease a clock skew being a difference of a clock propagation delay time is a very important technique for stabilizing the operation of the clock distributing circuit. If the clock skew is large, the receivers on the nets will have a problem with synchronizing operation on the nets; and therefore, the clock skew of the clock distributing circuit has to be reduced.
Further, to minimize the lengths of wirings to connect circuit elements on an LSI and to enhance quality of wiring is necessary to speed up the processes in the LSI.
In this case, to estimate a possibility of a wiring before executing the wiring and from the possibility to improve a layout of the circuits and to optimize a wiring area should also be considered.
Especially at present, a wiring objective is inclined to have a gigantic scale, and an early estimation and evaluation of the possibility of wirings has increased the need.
2. Description of the Related Art
There have been many reports on the wiring processing method for reducing the clock skew, namely, a difference of a clock propagation delay time in the clock synchronous circuit.
The IBM method will hereunder be described which is a typical wiring processing method for reducing the clock skew. This method is detailed in `Ren-Song Tsay, "Exact zero skew", Proc. IEEE Int. Conference on CAD, pp336-339, 1991`.
Before explaining the wiring processing method for reducing a clock skew, first, FIG. 34 illustrates a configuration of a clock tree in a clock net on a clock distributing circuit of a clock synchronous circuit.
A clock tree 130 comprises a sub-clock tree consisting of a clock receiver (receiving circuit) 112 and a wiring 118 and another sub-clock tree consisting of a clock receiver (receiving circuit) 115 and a wiring 121, which are connected at an equal delay branch point (tapping point) "x" where the sub-clock trees have an equal delay.
Thus, in the clock tree 130, a clock driver (clock generator) not illustrated in FIG. 34 supplies a clock signal to the receiver 112 and 115 through the equal delay branch point "x".
Here, the receiver 112 is composed of a flip-flop (time constant t.sub.1) 113 and a capacitor (capacitance C.sub.1) 114, and the receiver 115 is composed of a flip-flop (time constant t.sub.2) 116 and a capacitor (capacitance C.sub.2) 117.
The wire 118 forms a .PI. type RC circuit consisting of one resistor (resistance r.sub.1) 119 and two capacitors (capacitance c.sub.1 /2) 120.
Further, in the same manner as the wire 118, the wire 121 also forms the .PI. type RC circuit consisting of one resistor (resistance r.sub.2) 122 and two capacitors (capacitance c.sub.2 /2) 123.
Here, the reason that a wiring between the receiver 112 and 115 is represented by means of the one .PI. type RC circuit in FIG. 34 will now be described.
First, a close look at one sub-clock tree is requested.
FIG. 32 illustrates a model for a clock tree with a buffer, and as shown in this figure, the clock tree with a buffer 100 comprises a clock generator (clock source) 101 as the driver, a clock receiver (latch) 103 as the receiver, and a buffer 102 through which the former two are connected.
Here, the clock source 101 is connected to the buffer 102 through a wire 104 and the buffer 102 is connected to the latch 103 through the wire 105.
This clock tree 100 has a configuration as shown in FIG. 33 in detail.
The clock source 101 has a resistor (resistance r.sub.s) 106; the buffer 102 has a delay circuit (internal delay time d.sub.b) 111, a resistor (resistance r.sub.b) 107, and a capacitor (capacitance c.sub.b) 109; the latch 103 has a capacitor (capacitance c.sub.1) 110.
The delay time from the clock source 101 to the latch 103 includes the delay time due to the wiring resistors and capacitors of the wiring 104 and 105, and the internal delay time d.sub.b by the delay circuit 111 of the buffer 102.
The wiring resistor has become a big problem as not negligible, since the size of transistors and the cross-sectional area of wirings have decreased owing to the recent progress in the semiconductor microstructuring technique.
Accordingly, it has become necessary to deal with the wiring 104 and 105 as a distributed constant circuit from accuracy for estimating the delay time. Generally, as shown in FIG. 33, the wiring 104 and 105 have been evaluated by means of the .PI. type RC circuit composed of one resistor (resistance r.sub.s) 106 and two capacitors (capacitance c.sub.1 /2) 108 as a concentrated constant circuit being a typical form of the distributed constant circuit.
Incidentally, the equal delay branch point "x" is an input point of a clock from the driver (clock generator) not illustrated in FIG. 34.
In the clock tree 130 shown in FIG. 34, the clock skew by the two sub-clock trees of the clock tree 130 varies depending on the position of the equal delay branch point "x". Therefore, the position of the equal delay branch point "x" has to be set very accurately so as to reduce the clock skew in the clock tree 130.
According to the method (zero-skew-merge) to determine the equal delay branch point "x" in the wiring between the two sub-clock trees, the equal delay branch point "x" is known to satisfy the following equation. EQU r.sub.1 (c.sub.1 /2+C.sub.1)+t.sub.1 =r.sub.2 (c.sub.2 /2+C.sub.2)+t.sub.2.
Where L, .alpha., .beta. are given as below,
L: wiring length between the two sub-clock trees PA1 .alpha.: resistance for unit length of the line PA1 .beta.: capacitance for unit length of the line the equal delay branch point "x" is determined by the following: EQU x=[(t.sub.2 -t.sub.1)+.alpha.L (C.sub.2 +.beta.L/2)]/[.alpha.L (.beta.L+C.sub.1 +C.sub.2)]. PA1 r.sub.i : resistance across a segment PA1 c.sub.j : capacitance at a segment PA1 C.sub.A : capacitance at the one receiver PA1 C.sub.B : capacitance at the other receiver PA1 t.sub.A : delay time by the one receiver PA1 t.sub.B : delay time by the other receiver PA1 n+1: total number of the dividing points PA1 k: first number of the dividing points forming the equal delay branch segment. PA1 L: wiring length between the two receivers PA1 .alpha.: resistance for a unit length of the wiring PA1 .beta.: capacitance for a unit length of the wiring PA1 C.sub.A : capacitance at the one receiver PA1 C.sub.B : capacitance at the other receiver PA1 t.sub.A : delay time by the one receiver PA1 t.sub.B : delay time by the other receiver.
Incidentally, circuits on an LSI are connected through optimum wiring paths searched by means of an automatic wiring system.
There have been many reports on the automatic searching method for wiring paths, and the Mikami-Tabuchi method as a kind of the line segment searching method will hereafter be described.
The line segment searching method is a method to search wiring paths while sequentially generating vertical or horizontal probes, which has an advantage in a high speed processing with a small storage capacity.
In the Mikami-Tabuchi method, as shown in FIG. 35, first, temporal line segments of level 0 are generated in the horizontal direction from the search start point S and the search end point T. Where there is no overlapping with these temporal line segments, next, temporal line segments of level 1 intersecting vertically to the line segments of level 0 are generated.
And, repeating these steps, when the temporal line segments from both sides intersect, the intersecting line segments are searched backward, thereby finding a wiring path, for example, as shown in FIG. 36.
The Mikami-Tabuchi method can find a wiring path invariably where there is a wiring path, however, the number of the temporal line segments increases rapidly as the level increases, and in the worst case, as many temporal line segments as the number of the grids have to be searched. Thus, the method is applied wherein the level number of the temporal line segments is limited to, for example, 2 or 3.
However, in the clock tree 130 as shown in FIG. 34, the foregoing wiring 118 and 121 each are evaluated by means of a single .PI. type RC circuit (.PI. type RC model).
This is because the resistance and capacitance for each unit grid in the wiring on both sides of the equal delay branch point x are assumed equal regardless of the position in determining the equal delay branch point "x".
However in reality, it is impossible that the resistance and capacitance for each unit grid are equal regardless of the position; and therefore, it becomes necessary to determine the equal delay branch point "x" from the evaluation of a series .PI. type RC circuit (series .PI. type RC model) obtained by dividing the wiring 118 and 121 into a plurality of segments, which will be a problem to be solved.
Furthermore, in the clock tree 130 as shown in FIG. 34, there is another problem in determining the equal delay branch point "x" that the delay time from the clock driver to each of the clock receivers has to be set to a target value while considering gate delays (extra-source gate delay) increased by applying loads to the clock driver not illustrated.
In the Mikami-Tabuchi method being one method for automatic searching for wiring paths, the temporal line segments (search segments) of the same level are processed without influencing each other, and therefore, it is possible to speed up the search for the line segments when the processing of search segments can be executed in parallel.
However, in the Mikami-Tabuchi method, since a point once searched is not searched again, and when a wiring path not optimum is searched before an optimum wiring path is searched, the wiring path not optimum can possibly be selected, which is another problem.
Accordingly, to solve the problem requires a method whereby a plurality of wiring paths can be searched and an optimum wiring path can be selected therefrom.
Further as mentioned above, if the possibility of wiring can be estimated before executing a wiring in the design of an LSI, it will be possible to improve the layout of a circuit and to optimize a wiring area from the possibility of wiring.
However, it is difficult to know the wiring possibility of a wiring objective when finishing the layout of a circuit, and there is a problem that the wiring possibility cannot be known before finishing the wiring.